package leetcode;

public class DecodeWays91 {

	public static void main(String[] args) {
		System.out.println(numDecodings("4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"));
	}
	
	public static int numDecodings(String s) {
		int length = s.length();
		if(length == 0 || s.startsWith("0"))
			return 0;
		int[] history = new int[length];
		history[0] = 1;
		for(int i = 1; i < length; i++) {
			history[i] = history[i - 1];
			char first = s.charAt(i - 1);
			char second = s.charAt(i);
            int value = Integer.parseInt(first + "" + second);
            System.out.print(value + " ");
            if(first != '0' && second != '0'){
                if(value <= 26) {
                	if(i - 2 >= 0)
                		history[i] = history[i - 1] + history[i - 2];
                	else
                		history[i] = history[i - 1] + 1;
                }
            }
            else if(first != '0' && second == '0'){
                if(value > 26)
                    return 0;
                else
                    history[i] = i - 2 >= 0 ?history[i - 2]:1;
            }
            else if(first == '0' && second == '0'){
                return 0;
            }
            System.out.println(history[i]);
		}
		return history[length - 1];
	}
}
